{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 第11章-条件随机场-导读\n",
    "&emsp;&emsp;学习本章内容有两个方法：(1)可以对照第10章-隐马尔可夫模型，它们所要解决的问题属于标注问题，第10章是用有向图模型，第11章是用无向图模型来解决标注问题，第10章的第2、3、4节分别解决了隐马尔可夫模型三个问题，在第11章对应的第3、4、5节也分别解决了这三个问题；(2)第11章可以对照第6章学习，因为在条件随机场，使用因子模型表示概率模型时，实际上用的是对数线性模型，第6章的最大熵模型用的额也是对数线性模型，在求解的过程中有相通的地方，第11章也涉及到了改进的迭代尺度法和拟牛顿法。  \n",
    "\n",
    "### 概率无向图模型\n",
    "\n",
    "#### 概率图模型\n",
    "&emsp;&emsp;概率图模型一共分为有向图（贝叶斯网络）和无向图（马尔可夫随机场），有向图主要描述变量间的因果关系，用有向的边来表示因果关系；无向图是不带有箭头的边连接的随机变量。  \n",
    "\n",
    "> **定义11.1（概率无向图模型）**  \n",
    "&emsp;&emsp;设有联合概率分布$P(Y)$，由无向图$G=(V,E)$表示，$V$表示结点集合，$E$表示边集合，在图$G$中，结点表示随机变量，边表示随机变量之间的依赖关系。如果联合概率分布$P(Y)$满足成对、局部或全局马尔可夫性，就称此联合概率分布为概率无向图模型或马尔可夫随机场。\n",
    "\n",
    "#### 马尔可夫性\n",
    "<br/><center><img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../../../PhaseFour/Note/image/11-1-Local-Markov-Property.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图11-1 局部马尔可夫性</div></center>\n",
    "\n",
    "<br/><center><img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../../../PhaseFour/Note/image/11-2-Global-Markov-Property.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图11-2 全局马尔可夫性</div></center>  \n",
    "\n",
    "&emsp;&emsp;图11-1和图11-2是两个无向图模型，是由圆形的结点和边构成，结点表示随机变量，图中空心结点和带阴影的结点是为了介绍马尔可夫性，而不表示隐变量或可观测变量。在马尔可夫随机场中，用无向边连接两个结点，表示这两个结点的关系，但并不像有向图中，表示依赖（因果）关系。用图模型表示一个概率模型，最重要的就是图模型变量的依赖性或独立性。在无向图中，引入了马尔可夫性描述这种关系，书中介绍了三种：成对马尔可夫性、局部马尔可夫性和全局马尔可夫性。  \n",
    "&emsp;&emsp;**成对马尔可夫性：** 在图11-1中，一共有10个结点（即10个随机变量），任意找两个没有边直接连接的结点，假设有两个随机变量$(u,v)$没有边相连，剩下的8个随机变量记为$O$，当给定$O$时，$u$和$v$是独立的，即$P(u,v|O)=P(u|O)P(v|O)$。  \n",
    "&emsp;&emsp;**局部马尔可夫性：** 在无向图11-1中，任意找一个结点$v$，与$v$有边相连的所有结点记为$W$，其余5个结点记为$O$，当给定$W$时，$v$和$O$是独立的，即$P(v,O|W)=P(v|W)P(O|W)$。  \n",
    "&emsp;&emsp;**全局马尔可夫性：** 在无向图11-2中，一共有8个结点（即有8个随机变量），取中间两个随机变量记为集合$C$，当将集合$C$从图中删掉之后，那么剩下的6个结点分成了两个部分，可知左边的3个结点和右边的3个结点没有任何边将它们相连，当给定$C$时，$A$和$B$是独立的，即$P(A,B|C)=P(A|C)P(B|C)$。  \n",
    "&emsp;&emsp;为什么说这三个马尔可夫性是等价的？这里等价的意思为任意一个结点满足成对马尔可夫性等价于任意一个结点满足局部马尔可夫性，也等价于这些结点满足全局马尔可夫性。\n",
    "\n",
    "#### 概率无向图模型的因子分解\n",
    "&emsp;&emsp;无向图模型提供了一种分析随机变量之间关系的手段，当已知一组随机变量，能很清楚表达随机变量之间关系的方法是联合概率分布P(Y)，根据已知的无向图模型，可以得到联合概率分布$P(Y)$的形式。  \n",
    "\n",
    "<br/><center><img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../../../PhaseFour/Note/image/11-3-Clique-and-Maximum-Clique.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图11-3 无向图的团和最大团</div></center>\n",
    "\n",
    "**团：**在无向图模型中有一些结点（随机变量），这些结点中任意两个结点都有边相连，这些随机变量组成的集合称为团。如图11-3中，$Y_1$和$Y_2$有一条边相连，$\\{Y_1,Y_2\\}$可以称为一个团，同理$Y_2$和$Y_3$有一条边相连，$\\{Y_2,Y_3\\}$也可以称为一个团，不能将$\\{Y_1,Y_2,Y_4\\}$称为一个团，因为$Y_1$和$Y_4$之间是没有边相连的，$\\{Y_1,Y_2,Y_3\\}$可以组成一个团。  \n",
    "**最大团：**当给定一个团，在该团中不能再加进任何一个结点使其成为更大的团，比如$\\{Y_1,Y_2,Y_3\\}$就是一个最大团，\n",
    "\n",
    "> **定理11.1（Hammersley-Clifford定理）** 概率无向图模型的联合概率分布$P(Y)$可以表示为如下形式：$$P(Y)=\\frac{1}{Z} \\prod_C \\Psi_C(Y_C) \\\\\n",
    "Z=\\sum_Y \\prod_C \\Psi_C(Y_C)$$&emsp;&emsp;其中，$C$是无向图的最大团，$Y_C$是$C$的结点对应的随机变量，$\\Psi_C(Y_C)$是$C$上定义的严格正函数，乘积是在无向图所有的最大团上进行的，$\\Psi_C(Y_C) = \\exp\\{-E(Y_C)\\}$。$E(Y_C)$称为能量函数。\n",
    "\n",
    "&emsp;&emsp;在图11-3中先寻找最大团，易知$\\{Y_1,Y_2,Y_3\\}$和$\\{Y_2,Y_3,Y_4\\}$是最大团，可以写出联合概率分布$\\displaystyle P(y_1,y_2,y_3,y_4)=\\frac{1}{Z} \\Psi_1(y_1,y_2,y_3) \\Psi_2(y_2,y_3,y_4)$，这个联合概率分布可以表示为两个因子的乘积，每一个因子都是关于最大团的函数，前面$\\displaystyle \\frac{1}{Z}$保证概率分布对所有的随机变量求积分等于1，并且$\\Psi_1 \\geqslant 0,\\Psi_2 \\geqslant 0$。  \n",
    "\n",
    "#### 总结\n",
    "&emsp;&emsp;本节主要介绍概率无向图模型和因子分解（表示联合概率分布），这里介绍一些扩展内容，当表示一个随机向量各个分量之间的关系，概率$P(Y)$和一组随机变量的关系是一一对应的，即所有的随机变量都能表示成为一个概率分布，所有的概率分布都会一一对应一个随机向量。还介绍了，可以用有向图模型或者无向图模型表示概率分布，第10章的隐马尔可夫模型可以用有向图表示概率分布，第11章条件随机场可以用无向图表示概率分布。\n",
    "\n",
    "### 条件随机场的定义与形式\n",
    "\n",
    "#### 条件随机场的定义\n",
    "<br/><center><img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../../../PhaseFour/Note/image/11-4-Linear-Chain-CRF.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图11-4 线性链条件随机场</div></center>  \n",
    "\n",
    "&emsp;&emsp;如图11-4，如果只考察随机变量$Y=(Y_1,Y_2,\\cdots,Y_n)$，这些变量是用无向边连接的，属于无向图（马尔可夫随机场），但现在有另一组随机变量$X=(X_1,X_2,\\cdots,X_n)$，对每个随机变量$Y$都产生影响，由于$X$已知，在无向图中就添加了这样一个信息，$X$为条件，$X$和$Y$合起来称为条件随机场，由于$Y$是线性连接的，所以整个模型称为线性链条件随机场。$$P(Y_v|X,Y_w,w \\neq v) = P(Y_v|X,Y_w,w \\sim v)$$其中$v$表示任意一个结点，$w \\neq v$表示$v$以外的所有结点，$w \\sim v$表示与$v$有边连接的所有结点，上述等式表示给定$X，Y，w$的条件下，给定其他所有结点$v$的分布等于给定和它相邻的结点$v$的分布，其实是局部马尔可夫性。\n",
    "\n",
    "#### 条件随机场的参数化形式\n",
    "&emsp;&emsp;首先考察条件随机场的最大团个数，根据图11-4，最大团为$\\{Y_1,Y_2\\},\\{Y_2,Y_3\\}, \\cdots, \\{Y_{n-1},Y_n\\}$，所以条件随机场的因子分解（概率分布函数）是每一个最大团函数的乘积。  \n",
    "&emsp;&emsp;书中给出的条件随机场参数化形式如下：$$P(y|x)=\\frac{1}{Z(x)} \\exp\\left( \\sum_{i,k} \\lambda_k t_k (y_{i-1},y_i,x,i) + \\sum_{i,l}\\mu_l S_l(y_i,x,i)\\right)$$&emsp;&emsp;其中$\\displaystyle Z(x)=\\sum_y \\exp \\left( \\sum_{i,k} \\lambda_k t_k (y_{i-1},y_i,x,i) + \\sum_{i,l}\\mu_l S_l(y_i,x,i) \\right)$，因为是条件随机场，给定了变量$x$，再观察$\\displaystyle \\sum_{i,k} \\lambda_k t_k (y_{i-1},y_i,x,i)$，最大团的表示是$\\lambda_k t_k (y_{i-1},y_i,x,i)$，可以理解为$\\prod \\exp\\left(\\lambda_k t_k (y_{i-1},y_i,x,i)\\right)$，故最大团函数为$\\exp\\left(\\lambda_k t_k (y_{i-1},y_i,x,i)\\right)$，还多了一项$\\mu_l S_l(y_i,x,i)$，因为在无向概率图中还有一个$X$。  \n",
    "&emsp;&emsp;$t_k,s_l$是两个特征函数，在第6章介绍过特征函数，通常，特征函数$t_k,s_l$取值为1或0，当满足特征条件时取值为1，否则为0，$t_k$是关于$y_i,y_{i-1}$特征函数，$s_l$是关于$y_i$特征函数，函数$t_k$称为转移特征，函数$s_l$称为状态特征。条件随机场的参数是$\\lambda_k,\\mu_l$。  \n",
    "\n",
    "#### 条件随机场的简化形式\n",
    "$$P(y|x)=\\frac{1}{Z(x)} \\exp \\sum_{k=1}^K w_k f_k(y,x)$$其中$$Z(x)=\\sum_y \\exp \\sum_{k=1}^K w_k f_k(y,x) \\\\\n",
    "f_k(y_{i-1},y_i,x_i)=\\left \\{ \\begin{array}{l} \n",
    "t_k(y_k,y_i,x,i), \\quad k = 1,2,\\cdots,K_1 \\\\\n",
    "s_l(y_i,x,i), \\quad k=K_1+l;l=1,2,\\cdots,K_2\n",
    "\\end{array} \\right. \\\\\n",
    "w_k = \\left \\{ \\begin{array}{l} \n",
    "\\lambda_k,\\quad k = 1,2,\\cdots,K_1 \\\\\n",
    "\\mu_l, \\quad k=K_1+l;l=1,2,\\cdots,K_2\n",
    "\\end{array} \\right.\n",
    "$$\n",
    "\n",
    "#### 条件随机场的矩阵形式\n",
    "$$P_w(y|x)=\\frac{1}{Z_w(x)} \\prod_{i=1}^{n+1} M_i(y_{i-1}, y_i | x)$$其中$Z_w(x)$为规范化因子，是n+1个矩阵的乘积的(start,stop)元素：$$Z_w(x)+(M_1(x)M_2(x)\\cdots,M_{n+1}(x))_{\\text{start},\\text{stop}}$$\n",
    "\n",
    "### 条件随机场的概率计算问题\n",
    "&emsp;&emsp;条件随机场的概率计算问题等价于第10章的概率计算问题，利用条件随机场的矩阵形式，计算$P(Y=y_i|x)$，和第10章的区别是求解状态概率，而第10章求观测概率，本节采用的算法是前向-后向算法。  \n",
    "\n",
    "### 条件随机场的学习算法\n",
    "&emsp;&emsp;在对数线性模型中，参数$w$就是权重，这个权重包含转移特征、状态特征的权重，和第6章的算法类似，有两种算法：改进的迭代尺度法，拟牛顿法。这两个算法都用在对数线性模型中。  \n",
    "\n",
    "#### 条件随机场的预测算法\n",
    "在解决标注问题，采用的是维特比算法（动态规划），计算$y^*=\\mathop{\\arg \\max} \\limits_{y} P_w(y|x)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
